package com.fengye.algorithms.leecode.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author fengye
 * @Date 2023/4/17 4:35
 **/
public class TriangleMinimumTotal120 {

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3,4));
        triangle.add(Arrays.asList(6,5,7));
        triangle.add(Arrays.asList(4,1,8,3));

        System.out.println(new TriangleMinimumTotal120().minimumTotal(triangle));
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] f = new int[n];
        // 取第一个
        f[0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            // 先算出最外面的路径
            f[i] = f[i - 1] + triangle.get(i).get(i);
            // 算中间的路径
            for (int j = i - 1; j > 0; --j) {
                // 当前对应上面一个和左边一个中的最小的值
                f[j] = Math.min(f[j - 1], f[j]) + triangle.get(i).get(j);
            }
            // 算最左边的那一个
            f[0] += triangle.get(i).get(0);
        }
        int minTotal = f[0];
        // 遍历取出最小一个
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[i]);
        }
        return minTotal;
    }

}
